package solutions.leetcode.normal

import kotlin.math.absoluteValue

/**
 * @author lizhidong
 * <a href="https://leetcode.cn/problems/divide-two-integers/">29. 两数相除</a>
 */
class Solution29 {
    fun divide(dividend: Int, divisor: Int): Int {
        if (divisor == 0) {
            return 0
        }
        var step = Math.abs(divisor.toLong())
        var stepCount = 1L
        var count = 0L
        var remain = Math.abs(dividend.toLong())
        while (stepCount > 0) {
            if (remain > step) {
                count += stepCount
                remain -= step
                step = step shl 1
                stepCount = stepCount shl 1
            } else if (remain < step) {
                step = step shr 1
                stepCount = stepCount shr 1
            } else {
                count += stepCount
                break
            }
        }
        val rst = if ((dividend > 0 && divisor > 0) || (dividend < 0 && divisor < 0)) {
            count
        } else -count

        return if (rst > Int.MAX_VALUE || rst < Int.MIN_VALUE) {
            Int.MAX_VALUE
        } else {
            rst.toInt()
        }
    }
}

fun main() {
    println(Solution29().divide(-2147483648, -1))
}